package cn.aylog.simpleTree;

/**
 * 二叉树的遍历
 * 前序(根左右)
 * 中序(左根右)
 * 后序(左右根)
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "鲁智深");

        // binaryTree.setRoot(root);
        // root.setLeft(node2);
        // root.setRight(node3);
        // node3.setRight(node4);
        // node3.setLeft(node5);

        binaryTree.add(node3);
        binaryTree.add(root);
        binaryTree.add(node2);
        binaryTree.add(node4);
        binaryTree.add(node5);

        System.out.println("前序遍历"); // 1 2 3 4
        binaryTree.preOrder();
        //
        // System.out.println("中序遍历"); // 2 1 3 4
        // binaryTree.infixOrder();
        //
        // System.out.println("后序遍历"); // 2 4 3 1
        // binaryTree.postOrder();

        // System.out.println("前序查找");
        // System.out.println(binaryTree.preOrderSearch(15));
        //
        // System.out.println("中序查找");
        // System.out.println(binaryTree.infixOrderSearch(2));
        //
        // System.out.println("后序查找");
        // System.out.println(binaryTree.postOrderSearch(4));

        // System.out.println("删除节点");
        // HeroNode delNode = binaryTree.del(3);
        // System.out.println("前序遍历"); // 1 2 3 4
        // binaryTree.preOrder();
        // System.out.println("已删除节点"); // 1 2 3 4
        // delNode.preOrder();

    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (root != null) root.preOrder();
    }

    public void infixOrder() {
        if (root != null) root.infixOrder();
    }

    public void postOrder() {
        if (root != null) root.postOrder();
    }

    public HeroNode preOrderSearch(int id) {
        if (root != null) return root.preOrderSearch(id);
        return null;
    }

    public HeroNode infixOrderSearch(int id) {
        if (root != null) return root.infixOrderSearch(id);
        return null;
    }

    public HeroNode postOrderSearch(int id) {
        if (root != null) return root.postOrderSearch(id);
        return null;
    }

    public HeroNode del(int id) {
        HeroNode delNode = null;
        if (root != null) {
            if (root.getId() == id) {
                delNode = root;
                root = null;
            } else {
                delNode = root.del(id);
            }
        }
        return delNode;
    }

    public void add(HeroNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
}

class HeroNode {
    private int id;
    private String name;
    private HeroNode left;
    private HeroNode right;


    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) this.left.preOrder();
        if (this.right != null) this.right.preOrder();
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) this.left.infixOrder();
        System.out.println(this);
        if (this.right != null) this.right.infixOrder();
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) this.left.postOrder();
        if (this.right != null) this.right.postOrder();
        System.out.println(this);
    }

    /**
     * 前序查找
     */
    public HeroNode preOrderSearch(int id) {
        if (this.id == id) return this;
        HeroNode ret = null;
        if (this.left != null) ret = this.left.preOrderSearch(id);
        if (ret != null) return ret;
        if (this.right != null) ret = this.right.preOrderSearch(id);
        return ret;
    }

    /**
     * 中序查找
     */
    public HeroNode infixOrderSearch(int id) {
        HeroNode ret = null;
        if (this.left != null) ret = this.left.infixOrderSearch(id);
        if (ret != null) return ret;
        if (this.id == id) return this;
        if (this.right != null) ret = this.right.infixOrderSearch(id);
        return ret;
    }

    /**
     * 后序查找
     */
    public HeroNode postOrderSearch(int id) {
        HeroNode ret = null;
        if (this.left != null) ret = this.left.postOrderSearch(id);
        if (ret != null) return ret;
        if (this.right != null) ret = this.right.postOrderSearch(id);
        if (ret != null) return ret;
        if (this.id == id) return this;
        return null;
    }

    /**
     * 节点删除, 直接删除节点或数,不考虑移动
     */
    public HeroNode del(int id) {
        HeroNode delNode = null;
        if (this.left != null) {
            if (this.left.id == id) {
                HeroNode ret = this.left;
                this.left = null;
                return ret;
            } else {
                delNode = this.left.del(id);
            }
        }
        if (delNode != null) {
            return delNode;
        }

        if (this.right != null) {
            if (this.right.id == id) {
                HeroNode ret = this.right;
                this.right = null;
                return ret;
            } else {
                delNode = this.right.del(id);
            }
        }
        if (delNode != null) {
            return delNode;
        }
        return null;

        // if(this.left!=null && this.left.id != id) {
        //     this.left.del(id);
        // } else {
        //     this.left = null;
        // }
        //
        // if(this.right!=null && this.right.id != id) {
        //     this.right.del(id);
        // } else {
        //     this.right = null;
        // }
    }

    /**
     * 节点新增
     */
    public void add(HeroNode node) {
        if (this.id <= node.id) {
            if (this.right != null) {
                this.right.add(node);
            } else {
                this.right = node;
            }
        } else {
            if (this.left != null) {
                this.left.add(node);
            } else {
                this.left = node;
            }
        }
    }
}
